#include <iostream>
using namespace std;
template <typename T>
struct Node{
T key, value;
Node *p=nullptr, *left=nullptr, *right=nullptr;
Node(T _key, T _value): key(_key), value(_value) {}
};
template <typename T>
class BinaryTree{
public:
BinaryTree(){}
Node<T>* Root(void){
return this->root;
}
void InorderTreeWalk(Node<T>* x){
if(x!=nullptr){
InorderTreeWalk(x->left);
cout<<x->key<<endl;
InorderTreeWalk(x->right);
}
}
Node<T>* Search(Node<T>* x, T key){
if(x==nullptr || key==x->key) return x;
if(key<x->key) return Search(x->left, key);
else return Search(x->right, key);
}
Node<T>* IterativeSearch(Node<T>* x, T key){
while(x!=nullptr && key!=x->key){
if(key<x->key) x=x->left;
else x=x->right;
}
return x;
}
Node<T>* Minimum(Node<T>* x){
while(x->left!=nullptr) x=x->left;
return x;
}
Node<T>* Maximum(Node<T>* x){
while(x->right!=nullptr) x=x->right;
return x;
}
Node<T>* Successor(Node<T>* x){
if(x->right!=nullptr) return Minimum(x->right);
Node<T>* y=x->p;
while(y!=nullptr && x==y->right){
x=y;
y=y->p;
}
return y;
}
void Insert(int key, int value){
Node<T>* z=new Node(key, value);
Node<T> *x, *y;
x=this->root; y=nullptr;
while(x!=nullptr){
y=x;
if(z->key<x->key) x=x->left;
else x=x->right;
}
z->p=y;
if(y==nullptr) this->root=z;
else if(z->key<y->key) y->left=z;
else y->right=z;
}
void Transplant(Node<T>* u, Node<T>* v){
if(u->p==nullptr) this->root=v;
else if(u==u->p->left) u->p->left=v;
else u->p->right=v;
if(v!=nullptr) v->p=u->p;
}
void Delete(int key){
Node<T>* z=Search(this->root, key);
if(z->left==nullptr) Transplant(z, z->right);
else if(z->right==nullptr) Transplant(z, z->left);
else {
Node<T>* y=Minimum(z->right);
if(y->p!=z){
Transplant(y, y->right);
y->right=z->right;
y->right->p=y;
}
Transplant(z, y);
y->left=z->left;
y->left->p=y;
}
delete z;
}
private:
Node<T>* root=nullptr;
};
int main(void){
BinaryTree<int> tree;
tree.Insert(12, 12);
tree.Insert(5, 5);
tree.Insert(2, 2);
tree.Insert(9, 9);
tree.Insert(18, 18);
tree.Insert(15, 15);
tree.Insert(19, 19);
tree.Insert(13, 13);
tree.Insert(17, 17);
cout<<tree.Maximum(tree.Root())->value<<endl;
tree.Delete(19);
cout<<tree.Maximum(tree.Root())->value<<endl;
return 0;
}